#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/10/18 16:02|16:02
# @Author  : yangdingyi
# @File    : 2020-10-18.19.删除链表的倒数第N个节点
# @Software: PyCharm
from tools.my_methods import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        def dfs(rt, n):
            if not rt:
                return 0
            nn = dfs(rt.next, n)
            if nn == n:
                rt.next = rt.next.next
            return nn + 1

        hn = dfs(head, n)
        if hn == n:
            return head.next
        return head

